package likou;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/07/08 11:38
 */
public class _79 {
    public static void main(String[] args) {
        System.out.println(exist(new char[][]{{'a','a','C','E'}},"aaa"));
    }

    public static boolean exist(char[][] board, String word) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(word.charAt(0)==board[i][j]){
                    HashSet<Integer> set = new HashSet<>();
                    set.add(i*board[0].length+j);
                    if(fb(set,board,word,new int[]{i,j},1)){
                        return true;
                    }
                }

            }
        }
        return false;
    }
    static int[][] position = new int[][]{{0,1},{0,-1},{-1,0},{1,0}};
    public static boolean fb(Set<Integer> set, char[][] board, String word, int[] weizhi, int index){
        int row = board.length;
        int col = board[0].length;
        if(index == word.length()){
            return true;
        }
        for(int i=0;i<4;i++){
            int y = weizhi[0]+position[i][0];//行
            int x = weizhi[1]+position[i][1];//列
            int setWZ = y*col+x;
            if(y==row||y==-1||x==col||x==-1||set.contains(setWZ)||word.charAt(index)!=board[y][x]) continue;
            set.add(setWZ);
            if(fb(set,board,word,new int[]{y,x},index+1)){
                return true;
            }
            set.remove(setWZ);
        }
        return false;
    }
}
